# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        def advance(head, leng):
            while leng>0:
                head = head.next
                leng-=1
            return head
        
        def merge(head1, head2):
            head = ListNode(None)
            cur = head
            while head1 and head2:
                if head1.val<head2.val:
                    cur.next = head1
                    head1 = head1.next
                    cur = cur.next
                    cur.next = None
                else:
                    cur.next = head2
                    head2 = head2.next
                    cur = cur.next
                    cur.next = None
            while head1:
                cur.next = head1
                head1 = head1.next
                cur = cur.next
                cur.next = None
            while head2:
                cur.next = head2
                head2 = head2.next
                cur = cur.next
                cur.next = None
            return head.next

        def mergeSort(head, leng):
            if leng<=1:return head            
            newHead = ListNode(None)
            newHead.next = head
            head1 = head
            tail1 = advance(newHead, leng//2)
            head2 = tail1.next
            tail1.next = None
            head1 = mergeSort(head1, leng//2)
            head2 = mergeSort(head2, leng-leng//2)
            newHead.next = merge(head1, head2)
            return newHead.next

        def length(head):
            leng = 0
            while head:
                head = head.next
                leng+=1
            return leng
        
        return mergeSort(head, length(head))

head = ListNode(1)
Solution().sortList(None)